package 动态规划.另类的;

import 差分Plus离散化.美团流星差分solution;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/9 15:39
 */
public class lc6899达到末尾下标所需要的最大次数 {
    /*

     */


    public static int recursion(int index, int nums[], int target) {
        if (index == nums.length - 1) {
            return 0;
        }
        int ans = Integer.MIN_VALUE / 2; // 不能设置成 整型的最小值, 你懂得
        for (int i = index + 1; i < nums.length; i++) { // 枚举决策
            if (Math.abs(nums[i] - nums[index]) <= target) { // 决策的条件限制
                ans = Math.max(ans, recursion(i, nums, target) + 1);
            }
        }
        return ans;
    }


    public static int solution(int nums[], int target) {
        if (target == 0) {
            return -1;
        }
        int ans = recursion(0, nums, target);
        return -ans > nums.length ? -1 : ans;
    }


    public int dp(int nums[], int target) {
        int dp[] = new int[nums.length];
        for (int i = nums.length - 2; i >= 0; i--) {
            int ans = Integer.MIN_VALUE / 2;
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[j] - nums[i]) <= target) {
                    ans = Math.max(ans, dp[j] + 1);
                }
            }
            dp[i] = ans;
        }
        return  -dp[0] > nums.length ? - 1 : dp[0];
    }


    public static void main(String[] args) {
        int nums[] = {670355988, 886437985, 403625544, 333473422, -765827269, 468372740};
        int t = 70152122;
        int recursion = solution(nums, t);
        System.out.println(recursion);
    }
}
